#include "headfiles.h"
#include <string>

using namespace std;

// Compare two string, letter in the beginning have higher weight
// If string1 is before string2, return 1;
// If string1 is the same as string2, return 0;
// Otherwise, return -1;

int compareString(char *str1, char *str2) {
    string s1(str1);
    string s2(str2);

    size_t str1_len = s1.size();
    size_t str2_len = s2.size();

    size_t len = (str1_len < str2_len) ? str1_len : str2_len;
    size_t i;

    for (i = 0; i < len; i++) {
        if (str1[i] < str2[i]) {
            return 1;
        }
        else if (str1[i] > str2[i]) {
            return -1;
        }
    }

    if (str1_len == str2_len) {
        return 0;
    }
    else if (str1_len < str2_len) {
        return 1;
    }
    else {
        return -1;
    }
}

void quickSortStrings(char **str_array, int start, int end) {
    if (start >= end - 1) {
        return;
    }

    int pivot_loc = (start + end) / 2;
    char *str_pivot = str_array[pivot_loc];
    str_array[pivot_loc] = str_array[start];

    int loc = start;
    int l = loc + 1;
    int r = end;

    while (l < r) {
        if (compareString(str_array[l], str_pivot) != -1) {
            str_array[loc] = str_array[l];
            ++loc;
            ++l;
        }
        else {
            char *str_tmp = str_array[l];
            str_array[l] = str_array[r - 1];
            str_array[r - 1] = str_tmp;
            --r;
        }
    }

    str_array[loc] = str_pivot;

    quickSortStrings(str_array, start, loc);
    quickSortStrings(str_array, loc + 1, end);
}

bool sortStrings(char **str_array, int str_num) {
    if (str_array == NULL ||
        str_num <= 0) {
        cout << "Error, invalid input!" << endl;
        return false;
    }

    quickSortStrings(str_array, 0, str_num);

    return true;
}



